a=input("请输入列表元素")
k=eval(input("请输入k值"))
nums=[]
for i in range(len(a)):
    nums.append(eval(a[i]))
print(nums)

#-------方法一:冒泡排序-------
#时间复杂度为 O(n*n)
print("-------方法一:冒泡排序-------")
nums1=list(nums)
def find_max1(nums,k):
    for i in range(len(nums)-1):
        for j in range(len(nums)-1-i):
            if nums[j]<nums[j+1]:
                nums[j],nums[j+1]=nums[j+1],nums[j]
    return nums[k-1]
print("第%d大元素为%d"%(k,find_max1(nums1,k)))

#-------方法二:直接查找法-------
#平均时间复杂度为 O(n*k)
print("-------方法二:直接查找法-------")
nums2=list(nums)
def find_max2(nums,k):
    m=0
    for i in range(k):
        for j in range(len(nums)):
            if nums[m]<nums[j]:
                m=j
        if i!=k-1:
            del nums[m]
            m=0
    return nums[m]
print("第%d大元素为%d"%(k,find_max2(nums2,k)))

#-------方法三:使用最小堆---------
#平均时间复杂度: O(n log k)
print("-------方法三:使用最小堆---------")
import heapq
def find_max3(nums, k):
    min_heap = []

    for num in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        else:
            if num > min_heap[0]:
                heapq.heapreplace(min_heap, num)

    return min_heap[0]
print(f"第{k}大的元素是: {find_max3(nums, k)}")


#-------方法四:快速选择-------
#平均时间复杂度: O(n)
print("-------方法四:快速选择-------")
import random

def find_max4(nums, k):
    def quick_select(arr, k_largest):
        if len(arr) == 1:
            return arr[0]
        # 随机选择pivot
        pivot = random.choice(arr)
        # 分区
        left = [x for x in arr if x > pivot]
        mid = [x for x in arr if x == pivot]
        right = [x for x in arr if x < pivot]

        if k_largest <= len(left):
            return quick_select(left, k_largest)
        elif k_largest <= len(left) + len(mid):
            return mid[0]
        else:
            return quick_select(right, k_largest - len(left) - len(mid))
    return quick_select(nums, k)
print(f"第{k}大的元素是: {find_max4(nums, k)}")